#include<bits/stdc++.h>
#define ___ "-------------------------------\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll maxn = 100000 + 5;

class Solution {
public:
    vector<int> countBits(int n)
    {
        vector<int> dp(n + 1, 0);     // dp[i] 即 i 的二进制表示中 1 的个数
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) { // 这里注意运算符优先级的问题，不括括号会出问题
                highBit = i;
            }
            dp[i] = dp[i - highBit] + 1;
        }
        return dp;
    }
};

int main(){
//    ios::sync_with_stdio(false);
//    ifstream cin("data.txt");
//    freopen("data.txt", "r", stdin);
    return 0;
}

/**
 * @date 2022-09-13
 * @brief dp[i] = dp[i - 第一个小于等于 i 的 2 的整数次幂] + 1
 *      因为我们知道 2 的整数次幂的二进制中 1 的个数就是 1。
 *      他娘的 == 的优先级刚好比 & 高那么一丢丢
 */